package problems.practice;

/**
 * 316. 去除重复字母
 * <p>https://leetcode.cn/problems/remove-duplicate-letters/</p>
 *
 * @author habitplus
 * @since 2022/10/28 09:32
 */
public class T316 {
    public String removeDuplicateLetters(String s) {
        char[] chs = s.toCharArray();
        int[] cntMap = new int[26];
        boolean[] visited = new boolean[26];
        // 模拟单调栈
        StringBuilder ret = new StringBuilder();
        int k, last;
        // 建立hash计数表
        for (char c : chs) ++cntMap[c - 'a'];

        for (char ch : chs) {
            k = ch - 'a';
            // 当前字符没有统计过
            if (!visited[k]) {
                // 栈顶字符比当前字符大，且后续还有栈顶字符
                while (ret.length() > 0
                        && ret.charAt(last = ret.length() - 1) > ch
                        && cntMap[ret.charAt(last) - 'a'] > 0) {
                    visited[ret.charAt(last) - 'a'] = false;
                    ret.deleteCharAt(last);
                }

                visited[k] = true;
                ret.append(ch);
            }
            --cntMap[k];
        }

        return ret.toString();
    }
}
